IJCAI 2019 论文解读 | 基于超图网络模型的图网络进化算法
作者丨张云喆
单位丨暗物智能科技
研究方向丨NLP推理、数学符号推理
研究背景
现实生活中很多的数据可以用图（graph）来建模，比如社交网络数据，paper 引用数据等。对于 AI 而言，一个常见的任务是半监督分类，即对图中的每一个点进行分类，在仅有部分点有标注的情况下。
处理理此类问题，比较经典的方法是 GCN [1]，通过对相邻节点的特征聚合操作来对每个节点进行特征提取。GCN 等 GNN 模型对于节点之间的关系表征是二元的，即仅能表征两个节点 <e1,e2> 之间的关系，对于大于二元的关系组只能通过多个二元关系的方式去近似。
超图模型（Hypergraph）就是针对这种情况提出的一种网络结构 [2]。如图 1 所示，不同类型的数据中都存在着多元关系，超图模型的基本设定就是一个边可以包含大于 2 个点，去拟合多元关系。
然而超图模型和图模型存在着一样的问题，即大部分模型中节点之间的关系来自于数据本身的属性，是一种静态的关系。这样会导致模型忽视很多不包含在这些静态关系中的隐含关系。为此，本文提出了一种基于超图模型的网络进化算法，通过图卷积提取的特征来进一步挖掘新的关系，示意图如图 2 所示。在图网络的进化过程中，可以丢弃一些不重要的关系同时挖掘新的关系。
算法过程
整个算法流程分为三个部分，首先通过节点之间的关系对 hypergraph 进行构建，然后对提取出的 hypergraph 进行卷积操作提取特征，最后根据新的提取特征构建新的 hypergraph。三个流程加在一起就表示了一次图网络的进化，这种进化操作可以被叠加多次，使得节点之间的关系可以被多次调整。
Hypergraph Construction
根据节点特征构建 hypergraph 的流程如下：
构建过程结合了 KNN 和 Kmeans 的方法。我们首先要清楚 hypergraph 的表示通常采用邻接矩阵的形式，矩阵大小为 | V | * | E |，分别表示节点的数量和边的数量，其中有关系的节点和边 h(v, e) = 1, 其余的 h(v, e) = 0。
首先算法针对每一个节点，采用 knn 的方法找到和该节点最相似的 n 个节点，形成一个 hyperedge，我们就得到了 |V| 个 hyperedge。然后我们在利用 kmeans 方法在节点中圈出 K 个中心点，对于每⼀一个节点，我们将它归属到最近的 S 个中心点，这样我们又得到了 K 个新的 hyperedge。
Hypergraph Convolution
节点卷积时通过构建一个 k * k 的 transform matrix，来将节点的特征维度压缩到 k 维大小。通过 transform matrix 和节点特征的相乘来对同一个 hyperedge 内节点的相互关系进行建模和表示。最后经过一个卷积操作进行维度的压缩，得到和包含这些节点的边的特征。边（hyperedge）的卷积操作为对于每一个节点所关联的边集合中，通过上一步得到的每一条边的特征，首先通过 MLP 计算自己的权重，然后再根据得到的权重进行相加得到每个节点的特征。
实验结果
算法在两个数据上做的评测。
Cora 数据集，含有 2708 个节点和 5429 个边的关系，每个节点代表一篇学术文章，关系表示文章之间的相互引用，这是一个带有天然 hypergraph 结构的数据集。微博数据集，含有 5550 条推文， 推文包含文字以及图片，其中 4196 条为正向情感，1345 条为负向情感。
▲ 图7. ablation study of different modules
Cora 数据集的任务为半监督节点分类，一共有 7 个类别。文章 follow 了之前 SOTA 结果的实验设定，分别测试在不同 label 覆盖率下的节点分类准确率，可以看出算法对比其他方法有提升，并且在 label 覆盖比较低的时候提升比较明显。同时作者在该数据上做了 ablation study，通过移除 hypergraph 构建方式以及 graph evolve 的过程，实验结果都有些下降。
微博数据集是一个完全没有初始关系网络的数据集，因此算法可以测试通过特征相似度挖掘的关系是否行之有效。同时实验还比较了不同方法的训练时间，在这个任务上该方法超过了之前的一系列 SOTA 结果。
结论和分析
本文基于超图网络模型（hypergraph），构建了一种通过节点特征相似度来让图网络自我进化的算法。优势在于通过不断的迭代和挖掘可以构建初始状态不包含的关系属性，对于挖掘隐含的关系是一种比较有效的方法。这个方法给我们带来了一定的启发，同时我认为有几点方向值得继续探索：
实验中对于两个数据集，模型参数设定的 layer 都设定为 2 层，推测 layer 叠加过多可能会带来训练困难等问题，可能是一个值得思考和优化的地方。
利用 kmeans 和 knn 来构建 graph 的关系可能比较简单和易于实现，可以探索更高级的构建 graph 的方式，并且对 graph 的结构进行一些弱监督。
GNN 以及 hypergraph 网络模型目前重点的实验任务在于节点分类，关系的构建等，可以考虑利用 hypergraph 结构去辅助 NLP 任务做知识的推理。
点击以下标题查看更多往期内容：
让你的论文被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。
📝 来稿标准：
• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向）
• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接
• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志
📬 投稿邮箱：
• 投稿邮箱：hr@paperweekly.site
• 所有文章配图，请单独在附件中发送
• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。
▽ 点击 | 阅读原文 | 下载论文